import java.util.Arrays;

/**
 * 322. 零钱兑换
 */
public class Solution_322 {
    /**
     * 动态规划
     * <p>
     * 时间复杂度：O(coins.length * amount)
     * <p>
     * 空间复杂度：O(amount)
     */
    public int coinChange(int[] coins, int amount) {
        // dp[i] 为组成金额 i 所需最少的硬币数量
        int[] dp = new int[amount + 1];
        // 为啥 dp 数组初始化为 amount + 1 呢，
        // 因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），
        // 所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。
        Arrays.fill(dp, amount + 1);

        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        Solution_322 solution = new Solution_322();
        int[] coins = { 1, 2, 5 };
        int amount = 11;
        int ans = solution.coinChange(coins, amount);
        System.out.println(ans);
    }
}
